# 字符串的排列： https://leetcode-cn.com/problems/permutation-in-string/solution/python3gu-ding-hua-dong-chuang-kou-da-xi-yn9x/

# 自己写的思路
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
            可以看到只包含小写字母，且排列在s2中也必须是连续的。
            那么可以使用滑动窗口解题，窗口固定大小为 s1长度， 通过计数 来判断是否相等。
        """
        s1Len, s2Len = len(s1), len(s2)
        # 如果s1 长度大于s2，直接返回错误
        if s1Len > s2Len: return False 

        # 1. 首先统计字符个数
        s1Cnt = [0] * 26
        for c in s1: s1Cnt[ord(c) - ord("a")] += 1
        # 记录单词的 字符个数
        s1CharCnt = 0
        for num in s1Cnt:
            if num > 0: s1CharCnt += 1
            
        # 2. 先将窗口 设置为 s1长度
        subS2Cnt = [0] * 26
        i = j = 0
        # 计算匹配的字符数
        matchCharCnt = 0

        while j < s1Len:
            index = ord(s2[j]) - ord("a")
            subS2Cnt[index] += 1
            if subS2Cnt[index] == s1Cnt[index]:
                matchCharCnt += 1
            j += 1

        if matchCharCnt == s1CharCnt:
            return True

        # 3. 循环，窗口前移判断
        while j < s2Len:
            # 4. 前移需要去掉 左边第一个字符
            iIndex = ord(s2[i]) - ord("a")
            subS2Cnt[iIndex] -= 1
            # 这里需要注意， 不在 s1中的元素，一定不会影响到matchCharCnt， 但是当 当前字符是 s1中字符使，
            # 假如 是字符 a，出现两次。  那么当 删除两个a时，会减去两次就错了， 减一次时， 已经不匹配了，第二次不能再减掉。
            # 所以进行判断， 当前 加1等于 s1中字符数时，减掉一个不等了， 才去 减掉 matchCharCnt -= 1
            if subS2Cnt[iIndex] < s1Cnt[iIndex] and subS2Cnt[iIndex] + 1 == s1Cnt[iIndex]:
                matchCharCnt -= 1
            i += 1

            # 5. 右移加上一个字符
            jIndex = ord(s2[j]) - ord("a")
            subS2Cnt[jIndex] += 1
            if subS2Cnt[jIndex] == s1Cnt[jIndex]:
                matchCharCnt += 1
            # 判断当前移动后的窗口是否 等于 s1
            if matchCharCnt == s1CharCnt:
                return True
            j += 1 

        return False



s1 = "ab"
s2 = "eidboaoo"

s1 = "adc"
s2 = "dcda"

s1 = "hello"
s2 = "ooolleoooleh"

s1 = "trinitrophenylmethylnitramine"
s2 = "dinitrophenylhydrazinetrinitrophenylmethylnitramine"

s = Solution()
rst = s.checkInclusion(s1, s2)
print(rst)